An attribute-based AC (ABAC) policy defines access control permissions based on the attributes of the subject, of the resource, and of the action that the subject is to perform on the resource (e.g., read, write). When the policy is enforced in a computer system or computer network, it controls access to entities in the system or network and thereby influences their state of operation. A resource may be, inter alia, a portion of a personal storage quota, a business unit storage quota, an information retrieval system, a (portion of a) database, an online service, a protected webpage or a physical device.
There currently exist general-purpose AC languages that have the richness to express fine-grained conditions and conditions which depend on external data. One particular example of an AC language is the eXtensible Access Control Markup Language (XACML) which is the subject of standardization work in a Technical Committee within the Organization for the Advancement of Structured Information Standards (see http://www.oasis-open.org). A policy encoded with XACML consists of functional expressions in attribute values, and the return value (decision) of the policy is one of Permit, Deny, Not Applicable, or Indeterminate. An XACML policy can apply to many different situations, that is, different subjects, resources, actions and environments and may give different results for different combinations of these. The XACML specification defines how a policy is evaluated for a request (or access request), particularly what policy attributes are to be evaluated or, at least, which values are required to exist for a successful evaluation to result. Key characteristics of this evaluation process are that the access request (the query against the policy) must describe the attempted access to a protected resource fully. In practice, it may be that the request is constructed in multiple stages by different components, so that a PEP (Policy Enforcement Point) provides only some initial attribute values and a PDP (Policy Decision Point) or other components can dynamically fetch more attribute values from remote sources as they are needed. Rules in an ABAC policy may be nested in a conditional fashion, so that attribute values—both those provided initially in the access request and those fetched from remote sources—will influence what further rules are to be applied. Based on a policy or policy set (unless otherwise indicated, these terms are used interchangeably herein) that covers a broad range of resources and subjects and a given request, it is often possible to obtain a decision by evaluating only a fraction of all functional expressions in the policy. Conversely, it cannot always be ascertained prima facie whether a request contains enough attribute values to allow a successful policy evaluation.
A reverse query works in the opposite direction. It defines an expected decision and constraints over the set of possible access requests, and is resolved by finding the set of access requests that (a) fulfill all the constraints, and (b) evaluate to the expected decision. Reverse queries have many uses. For instance, they could be used to determine the list of resources that a subject may access, or the list of subjects that may access a resource. Furthermore, many types of policy analyses can be built using reverse queries (e.g., Segregation of Duty validation).
The semantics of an XACML policy P may be given as a function fp mapping a request to a decision:fp: Request→DecisionIn many situations, however, it is necessary to evaluate the inverse of the policy function,(fp)−1: Decision→Set(Request)Given a decision d, (fp)−1(d) is the set of all requests that evaluate to d. For example, (fp)−1(PERMIT) is the set of all requests that are permitted by the policy P. Note that (fp)−1 is multi-valued in general, and may be regarded as a mapping from a decision value (Permit, Deny, etc.) to a set of requests.
In many important applications, there is a priori a set R of interesting requests. For instance, to determine all the users that may “read” a certain file “F”, only requests that identify the action as “read” and the resource as “file F” are of interest. In other words, what needs to be computed is actually the intersection of (fp)−1(d) with R,(fp)−1(d)∩R. 
These concepts may be summarized by the following definitions.
Definition (Reverse Query): A reverse query is a triple <P, d, R> where P is a policy, d is a decision and R is a set of requests.
Definition (Reverse Query Evaluation): A reverse query <P, d, R> is evaluated by computing (fp)−1(d)∩R, where fp is the semantic function associated to policy P.
The evaluation of a reverse query is in general much more demanding, in terms of computing resources, in particular, time, than evaluating a request against a policy. If the set of requests of interest, R={r1, . . . , rn}, contains a relatively small number of requests then the reverse query <P, d, R> may be effectively evaluated by computingfp(r1), . . . , fp(rn)and picking only those requests which evaluate to d. That is, a reverse query can be evaluated by sending each request of interest to the PDP (loaded with the policy P) and then comparing the returned decision with the expected decision d.
If the set R is large, however, the method described above becomes impracticable, particularly in situations where the reverse query needs to be evaluated in real-time, e.g., in the context of an interactive system where a user would be waiting in real time for the result of such evaluation.